/*
https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
 */
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Solution239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> queue=new LinkedList<>();
        int[] ans=new int[nums.length-k+1];
        for (int i=0;i<k;i++){
            while (!queue.isEmpty() && nums[queue.peekLast()]<=nums[i]){
                queue.pollLast();
            }
            queue.offer(i);
        }
        ans[0]=nums[queue.peekFirst()];
        for (int i=k;i<nums.length;i++){
            while (!queue.isEmpty() && nums[queue.peekLast()]<=nums[i]){
                queue.pollLast();
            }
            queue.offer(i);
            while (i-k>=queue.peekFirst()){
                queue.pollFirst();
            }
            ans[i-k+1]=nums[queue.peekFirst()];
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution239().maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3)));
    }
}
